public class Solution343 {
    /**
     * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
     */
    public int integerBreak(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 1;
        if (n == 3) return 2;
        int x = n / 3;
        int y = n % 3;
        int res = 1;
        for (int i = 0; i < x - 1; i++) {
            res *= 3;
        }
        switch (y){
            case 0:
                res *= 3;
                break;
            case 1:
                res *= 4;
                break;
            case 2:
                res *= 6;
                break;
        }
        return res;
    }

    public int integerBreak2(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i;j++){
                dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
            }
        }
        return dp[n];
    }
}
